#include <iostream>
#include "GraphFlow.h"
#include <stack>
#include <queue>
#include <typeinfo>
#include "GraphOrientedMatrix.h"
#include "GraphOrientedList.h"
#include "GraphFlowMatrix.h"
#include "GraphFlowList.h"
#include <string>
#include <unistd.h>
#include <cmath>

using namespace std;

GraphFlow::GraphFlow() : GraphOriented() {}
GraphFlow::GraphFlow(summit_t n, edges_t m) : GraphOriented(n,m) {}
GraphFlow::~GraphFlow() {}

void GraphFlow::fill(flow_t min_c, flow_t max_c)
{
  summit_t n = getSummitNb();
  edges_t m = getEdgesNb();
  
  if((n > 1) && (m >= 1)){
    if (m>(edges_t)(n*(n-1))/2)
    {
      cerr<<"Graphe impossible à réaliser : nombre d'arêtes trop élevé.\nPour ce graphe de type réseau de "<<n<<" sommets, "<<(n*(n-1))/2<<" arêtes maximum possibles"<<endl;
      return;
    }
    
    summit_t max_path_len = (n < m-1)?n:m-1; //Le nombre de sommets du chemin est le minimum entre le nombre de sommets et le nombre d'arêtes moins une
    summit_t path_len;
    if (max_path_len <= 2)
      path_len = 2;
    else
      path_len = rand()%(max_path_len-2)+2; //Génération aléatoire du nombre de sommets dans le chemin(compris entre 2 et min(n, m-1))
    // cout<<"Construction d'un chemin de "<<path_len<<" sommets"<<endl;
    flow_t c;
    summit_t cpt_s = 0;//Nombre de sommets dans notre graphe
    edges_t cpt_e = 0; //Nombre d'arêtes dans notre graphe
    bool * already_seen = new bool[n] ;//Table des sommets déjà vu. Au départ on ne connait rien.
    for(int i = 0; i < n; ++i){
      already_seen[i] = false;
    }
    //Initialisation : création d'un chemin de s à p
    already_seen[0] = true; //Début du chemin : s
    summit_t summit;
    summit_t tmp =  0;//Permet de stocker le sommet précédent dans le chemin, inialisé à 0 (s)
    for (int i = 0; i < path_len - 2; ++i){ //On tire au sort des sommets qui composeront le chemin en les connectant de la sorte : le 2e au 3e, le 3e au 4e, etc. jusqu'à avoir avant avant dernier et avant dernier (s -> 2e et avant dernier -> p est déjà fait)
      summit = rand()%(n-2)+1; //On tire au sort un sommet entre 1 et n-2 (on peut exclure a priori s et p donc 0 et n-1)
      while (already_seen[summit]){
	summit = (summit+1)%(n-2); //On évite les doublons. Pour ne pas trop boucler en aléatoire, on incrémente de 1 si la première position était occupée
      }
      connect(tmp, summit);
      c=min_c+(rand()%(1 + max_c - min_c));
      setCapacity(tmp,summit,c);
      already_seen[summit] = true;
      tmp = summit;
    }
    connect(tmp, n-1); //On relie l'avant dernier sommet à p
    c=min_c+(rand()%(1 + max_c - min_c));
    setCapacity(tmp,n-1,c);
    already_seen[n-1] = true;
    cpt_s = path_len;
    cpt_e = path_len - 1; //On a construit un chemin de taille path_len entre s et p, on a donc utilisé path_len-1 arêtes

    /*
     * Premier chemin de s à t généré.
     * On construit maintenant le reste des arêtes.
     */
    
    //Remplissage : on tire au sort tant que le nombre d'arêtes ou le nombre de sommets ne soit pas atteint.
    //Si sommet jamais vu : on ajoute une arête vers un sommet et on incrémente cpt_s et cpt_e
    //Si sommet déjà vu : on ajoute une arête vers un sommet  et on incrémente que cpt_e
    
    summit_t neighbour;
    while((cpt_e < m)){
      neighbour=rand()%(n-1)+1;
      if (neighbour==0)
	neighbour++;
      summit = rand()%(n-1);

      if (cpt_s >= n)
      {
	while ((summit==neighbour) || (not already_seen[summit]) || (areConnected(summit,neighbour)) || (areConnected(neighbour,summit)))
	{
	  neighbour=(neighbour+1)%(n);
	  if (neighbour==0)
	    neighbour++;
	  for (int i=0; i<n-1; i++)
	  {
	    summit = (summit+1)%(n-1);
	    if ((summit!=neighbour) && (already_seen[summit]) && (not areConnected(summit,neighbour)) && (not areConnected(neighbour,summit)))
	      break; //On a trouvé la paire
	  }
	}
      }
      else
      {
	while ((summit==neighbour) || (already_seen[neighbour]) || (not already_seen[summit]) || (areConnected(summit,neighbour)) || (areConnected(neighbour,summit)))
	{
	  neighbour=(neighbour+1)%(n);
	  if (neighbour==0)
	    neighbour++;
	  if ((not already_seen[neighbour]) && (degreeOf(neighbour)<(edges_t)n-1)) //Si il existe un sommet non-connecté à neighbour
	  {
	    for (int i=0; i<n-1; i++)
	    {
	      summit = (summit+1)%(n-1);
	      if ((already_seen[summit]) && (not areConnected(summit,neighbour)) && (not areConnected(neighbour,summit)))
		break; //On a trouvé la paire
	    }
	  }
	}
	already_seen[neighbour]=true;
	++cpt_s;
      }
      connect(summit, neighbour);
      c=min_c+(rand()%(1 + max_c - min_c));
      setCapacity(summit,neighbour,c);
      ++cpt_e;
    }
    delete [] already_seen;
  }
  else {
    cerr<<"Erreur dans les valeurs des paramètres du remplissage de Graph\n"
	<<"Nombre arêtes attendu ≥ 1, reçu "<<m<<". Nombre de sommets attendu ≥ 2, reçu "<<n
	<<endl;
    exit(1);
  }
}

flow_t GraphFlow::lowestDelta(vector<summit_t> * path, summit_t &u, summit_t &v) const
{
  flow_t min=(flow_t)-1;
  flow_t temp;
  u=(summit_t)-1;
  v=(summit_t)-1;

  if (path==NULL || path->size()<2)
    return -1;
  
  for (size_t i(1); i<path->size(); i++)
  {
    temp=getCapacity(path->at(i-1),path->at(i)) - getFlow(path->at(i-1),path->at(i));
    if ((min==(flow_t)-1) || (min>temp))
    {
      u=path->at(i-1); v=path->at(i);
      min=temp;
    }
  }
  return min;
}

flow_t GraphFlow::lowestDelta(vector<summit_t> * path) const
{
  summit_t u, v;
  return lowestDelta(path,u,v);
}

vector<summit_t> * GraphFlow::notSaturatedShortestPath(summit_t a, summit_t b) const
{
  if (a==b)
  {
    return NULL;
  }
  
  summit_t * father = new summit_t [summit_nb];
  for (int k(0); k<summit_nb; k++)
  {
    father[k]=(summit_t)-1;
  }
  vector<summit_t> * neighbours;
  queue<summit_t> * s_queue = new queue<summit_t>;
  bool foundPath=false;
  summit_t s_temp;

  s_queue->push(a); //Ajout du sommet source à la liste
  father[a] = a;
  while ((not s_queue->empty()) && (not foundPath))
  {
    s_temp = s_queue->front(); s_queue->pop(); //Récupère le premier élément de la file, puis le supprime
    neighbours = getNeighbours(s_temp);
    for (size_t k(0); k<neighbours->size(); k++)
    {
      if ((father[neighbours->at(k)] == (summit_t)-1) && (getFlow(s_temp,neighbours->at(k))<getCapacity(s_temp,neighbours->at(k)))) //Si l'on a jamais vu le sommet
      {
	father[neighbours->at(k)]=s_temp;
	s_queue->push(neighbours->at(k));
	if (neighbours->at(k) == b) //Si c'est le sommet d'arrivée
	{
	  foundPath=true;
	  break; //On quitte la boucle for
	}
      }
    }
    delete neighbours; //On désalloue la mémoire allouée par la méthode getNeighbours()
  }
  
  vector<summit_t> * path=NULL;
  stack<summit_t> * s_stack=NULL;
  
  if (foundPath)
  {
    path = new vector<summit_t>;
    s_stack = new stack<summit_t>;
    
    s_stack->push(b);
    do
    {
      s_stack->push(father[s_stack->top()]); //Ajout du père de l'élément précédent
    } while (s_stack->top() != a);
    
    while (not s_stack->empty())
    {
      path->push_back(s_stack->top());
      s_stack->pop();
    }
    delete s_stack;
  }
    
  delete [] father;
  delete s_queue;
  if ((path!=NULL) && (path->size()>1)) //On envoie le vecteur seulement s'il n'est pas vide
    return path;
  if (path!=NULL)
    delete path;
  return NULL;
}

vector<summit_t> * GraphFlow::notSaturatedShortestPath() const
{
  return notSaturatedShortestPath(0,summit_nb-1); //s = 0 et t = (nombre de sommets - 1)
}

vector<summit_t> * GraphFlow::notSaturatedPath(summit_t a, summit_t b) const
{
  if (a==b)
  {
    return NULL;
  }

  bool found_path=false;
  stack<summit_t> * s_stack = new stack<summit_t>;
  summit_t s_temp;
  vector<summit_t> * neighbours;
  summit_t * father = new summit_t [summit_nb];
  for (summit_t i=0; i<summit_nb; i++)
  {
    father[i]=(summit_t)-1;
  }

  father[a] = a;
  s_stack->push(a);
  while ((not s_stack->empty()) && (not found_path))
  {
    s_temp = s_stack->top(); s_stack->pop();
    neighbours = getNeighbours(s_temp);
    for (size_t i=0; i<neighbours->size(); i++)
    {
      if ((father[neighbours->at(i)] == (summit_t)-1) && ((getCapacity(s_temp,neighbours->at(i))>getFlow(s_temp,neighbours->at(i))))) //Sommet jamais vu
      {
	s_stack->push(neighbours->at(i));
	father[neighbours->at(i)]=s_temp;
	if (neighbours->at(i) == b)
	{
	  found_path=true;
	  break;
	}
      }
    }
    delete neighbours;
  }

  vector<summit_t> * path = NULL;
  while (not s_stack->empty())
    s_stack->pop();
  
  if (found_path)
  {
    path = new vector<summit_t>;
    
    s_stack->push(b);
    do
    {
      s_stack->push(father[s_stack->top()]); //Ajout du père de l'élément précédent
    } while (s_stack->top() != a);
    
    while (not s_stack->empty())
    {
      path->push_back(s_stack->top());
      s_stack->pop();
    }
  }
    
  delete [] father;
  delete s_stack;
  if ((path!=NULL) && (path->size()>1)) //On envoie le vecteur seulement s'il n'est pas vide
  {
    return path;
  }
  if (path!=NULL)
    delete path;
  return NULL;
  
  return path;
}

vector<summit_t> * GraphFlow::notSaturatedPath() const
{
  return notSaturatedPath(0,summit_nb-1);
}

void GraphFlow::updateResidualGraph(vector<summit_t> * path, flow_t k)
{
  //Chaîne augmentante path, delta = k
  if (not isResidual)
  {
    isResidual = true;
    for (summit_t i=0; i<summit_nb; i++)
    {
      for (summit_t j=0; j<summit_nb; j++)
      {
	if (areConnected(i,j))
	{
	  setCapacity(j,i,getCapacity(i,j)); //Capacité max de l'arc arrière
	}
      }
    }
  }
  
  summit_t u, v, changed=0;
  flow_t f;
  bool put_it_back=false;
  
  if ((path==NULL) || (path->size()<2))
  {
    //cerr<<"Chaîne augmentante invalide"<<endl;
    return;
  }
  if (k==(flow_t)-1)
  {
    cerr<<"Delta invalide"<<endl;
    return;
  }
  
  u=path->at(0);
  for (size_t i=1; i<path->size(); i++)
  {
    v=path->at(i);
    f = 0;
    if (getCapacity(u,v)>getFlow(u,v))
    {
      f=getCapacity(u,v)-getFlow(u,v);
    }
    if (k>f)
    {
      cerr<<"Erreur lors de la mise à jour du graphe d'écart : le flot ne peut être négatif (delta = "<<k<<")"<<endl;
      /*for (size_t j=1; j<path->size(); j++) {
	summit_t v = path->at(j), u=path->at(j-1);
	cout<<u<<"-"<<v<<" "<<getFlow(u,v)<<"/"<<getCapacity(u,v);
	if (j>changed)
	  cout<<"\t\tinchangé";
	cout<<endl;
	}*/
      put_it_back = true;
      break;
    }
    f=getFlow(u,v)+k;
    setFlow(u,v,f);
    //cout<<"Flot sur "<<u<<"-"<<v<<" = "<<f<<endl;
    connect(v,u);
    setFlow(v,u,getCapacity(u,v)-getFlow(u,v)); //Arc arrière mis à jour
    changed++;
    u=v;
  }

  if (put_it_back) //Pour revenir sur le graphe de départ si erreur
  {
    u=0;
    cerr<<"Annulation des changements..."<<endl;
    for (size_t i=1; i<changed; i++)
    {
      v=path->at(i);
      setFlow(u,v,getFlow(u,v)-k);
      setFlow(v,u,getFlow(v,u)+k);
      if (getFlow(u,v)==0)
	deconnect(v,u);
    }
  }
}

flow_t GraphFlow::getMaxCapacity() const
{
  flow_t c = 0;
  for (summit_t i=0; i<summit_nb; i++)
  {
    for (summit_t j=0; j<summit_nb; j++)
    {
      if ((areConnected(i,j)) && (c<getCapacity(i,j)))
	c=getCapacity(i,j);
    }
  }
  return c;
}

flow_t GraphFlow::getNetworkFlow() const
{
  summit_t t = summit_nb-1;
  flow_t f=0;
  for (summit_t i=0; i<summit_nb; i++)
  {
    if (i==t)
      continue;
    if (areConnected(i,t) && (getFlow(i,t)!=(flow_t)-1))
    {
      f+=getFlow(i,t);
    }
  }
  return f;
}

flow_t GraphFlow::doEdmondsKarp()
{
  flow_t sum_flow = 0;
  flow_t delta;
  vector<summit_t> * path;

  while ((path = notSaturatedShortestPath()))
  {
    /*for (summit_t i=0; i<summit_nb; i++)
    {
      for (summit_t j=0; j<summit_nb; j++)
      {
	cout<<areConnected(i,j)<<" ";
      }
      cout<<endl;
      }*/
    delta = lowestDelta(path);
    updateResidualGraph(path,delta);
    delete path;
    sum_flow+=delta;
  }
  return sum_flow;
}

flow_t GraphFlow::doDinic()
{
  flow_t sum_flow=0, delta;
  vector<summit_t> * path;
  updateResidualGraph(NULL,-1);
  GraphOriented * levelGraph;
  if (typeid(GraphFlowMatrix) == typeid((*this))) {
    levelGraph = new GraphOrientedMatrix(summit_nb,0);
  }
  else {
    if (typeid(GraphFlowList) == typeid((*this))) {
	levelGraph = new GraphOrientedList(summit_nb,0);
      }
    else {
      cerr<<"Erreur lors de l'introspection."<<endl;
      return 0;
    }
  }
  bool no_more = false;
  while (not no_more)
  {
    levelGraph->updateLevelGraph((*this)); //Construction complète à partir du graphe d'écart courant
    no_more = true;
    while ((path=levelGraph->onePath())) //Tant qu'il existe un chemin de s à t dans le graphe de couches
    {
      no_more = false;
      delta=lowestDelta(path); //On récupère le delta sur le graphe courant (graphe d'écart)
      sum_flow+=delta;
      updateResidualGraph(path,delta); //Augmentation de la chaîne améliorante de +delta
      levelGraph->updateLevelGraph((*this),path,delta); //On adapte le graphe de couche en supprimant les arêtes saturées
                                                        //à l'ajout d'un flot = delta et on supprime les culs de sac
      delete path;
    }
  }
  delete levelGraph;
  return sum_flow;
}

flow_t GraphFlow::doFordFulkerson()
{
  flow_t sum_flow=0, delta;
  vector<summit_t> * path;
  
  while ((path=notSaturatedPath()))
  {
    delta=lowestDelta(path);
    updateResidualGraph(path,delta);
    delete path;
    sum_flow+=delta;
  }
  return sum_flow;
}

/*flow_t GraphFlow::doCapacityScaling()
{
  flow_t sum_flow=0;
  //Cette prochaine étape peut être passé si on commence par un graphe vierge
  // for (summit_t i=0; i<summit_nb; i++)
  // {
  //     for (summit_t j=0; j<summit_nb; j++)
  //     {
  // 	setFlow(i,j,0); //Peu importe s'ils sont connectés ou non (plus efficace pour les listes...)
  //     }
  // }

  GraphOriented * g = new GraphOrientedMatrix(summit_nb,0);

  vector<summit_t> * path;
  summit_t u, v;
  flow_t little_d, big_d;
  big_d = pow(2,(int)log2(getMaxCapacity()));
  //Première construction
  while (big_d>=1)
  {
    g->updateCapacityScallingGraph((*this),big_d);
    while ((path=g->onePath()))
    {
      little_d = lowestDelta(path);
      sum_flow+=little_d;
      u=path->at(0);
      for (size_t i=1; i<path->size(); i++) //Mise à jour du flot
      {
	v=path->at(i);
	setFlow(u,v,(getFlow(u,v)+little_d));
	u=v;
      }
      g->updateCapacityScallingGraph((*this),big_d,path); //Aucune arête ajoutée, des arêtes de path sont enlevées
      delete path;
    }
    big_d/=2;
  }

  delete g;
  return sum_flow;
}
*/
flow_t GraphFlow::doCapacityScaling()
{
  flow_t sum_flow=0;

  vector<summit_t> * path;
  summit_t u, v;
  flow_t little_d, big_d;
  big_d = pow(2,(int)log2(getMaxCapacity()));

  while (big_d>=1)
    {
      while ((path=onePathCapacityScaling(big_d)))
	{
	  little_d = lowestDelta(path);
	  sum_flow+=little_d;
	  u=path->at(0);
	  for (size_t i=1; i<path->size(); i++) //Mise à jour du flot
	    {
	      v=path->at(i);
	      setFlow(u,v,(getFlow(u,v)+little_d));
	      u=v;
	    }
	  delete path;
	}
      big_d/=2;
    }
  return sum_flow;
}


vector<summit_t> * GraphFlow::onePathCapacityScaling(summit_t a, summit_t b, flow_t cmin) const
{
  if (a==b)
  {
    return NULL;
  }

  bool found_path=false;
  stack<summit_t> * s_stack = new stack<summit_t>;
  summit_t s_temp, n_temp;
  vector<summit_t> * neighbours;
  summit_t * father = new summit_t [summit_nb];
  for (summit_t i=0; i<summit_nb; i++)
  {
    father[i]=(summit_t)-1;
  }

  father[a] = a;
  s_stack->push(a);
  while ((not s_stack->empty()) && (not found_path))
  {
    s_temp = s_stack->top(); s_stack->pop();
    neighbours = getNeighbours(s_temp);
    for (size_t i=0; i<neighbours->size(); i++)
    {
      n_temp = neighbours->at(i);
      if ((father[n_temp] == (summit_t)-1) && ((getCapacity(s_temp,n_temp)-getFlow(s_temp,n_temp))>=cmin))
      {
	s_stack->push(neighbours->at(i));
	father[neighbours->at(i)]=s_temp;
	if (neighbours->at(i) == b)
	{
	  found_path=true;
	  break;
	}
      }
    }
    delete neighbours;
  }

  vector<summit_t> * path = NULL;
  while (not s_stack->empty())
    s_stack->pop();
  
  if (found_path)
  {
    path = new vector<summit_t>;
    
    s_stack->push(b);
    do
    {
      s_stack->push(father[s_stack->top()]); //Ajout du père de l'élément précédent
    } while (s_stack->top() != a);
    
    while (not s_stack->empty())
    {
      path->push_back(s_stack->top());
      s_stack->pop();
    }
  }
    
  delete [] father;
  delete s_stack;
  if ((path!=NULL) && (path->size()>1)) //On envoie le vecteur seulement s'il n'est pas vide
  {
    return path;
  }
  if (path!=NULL)
    delete path;
  return NULL;
  
  return path;
}

vector<summit_t> * GraphFlow::onePathCapacityScaling(flow_t cmin) const
{
  return onePathCapacityScaling(0,summit_nb-1,cmin);
}
